package com.base.search.impl.binarysearch;

/**
 * @ClassName: SearchRange
 * @Description: 34. 在排序数组中查找元素的第一个和最后一个位置
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 * <p>
 * 进阶：
 * <p>
 * 你可以设计并实现时间复杂度为O(log n)的算法解决此问题吗
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: li
 * @Date: 2021/8/24 6:52 下午
 */
public class SearchRange {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = {-1, -1};
        if (nums.length == 0) {
            return ret;
        }
        if (nums.length == 1&&nums[0] == target){
            return new int[]{0,0};
        }
        // [left,right]范围
        int left = 0, right = nums.length - 1;
        // 思路：先二分查找，知道找到元素，然后在找到的元素左右两边探索查找。
        while (left < right) {
            //防止左右相加超出范围
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                //找到的元素左右两边探索查找
                ret[0] = mid;
                ret[1] = mid;
                while (ret[0]-1 >= 0 && nums[ret[0]-1] == target) {
                    ret[0]--;
                }
                while (ret[1]+1 <= nums.length - 1 && nums[ret[1]+1] == target) {
                    ret[1]++;
                }
                break;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid;
            }
        }
        return ret;
    }
    /**
     * 两次查询，先找左侧边界，在找右侧边界
     */
    public int[] searchRange1(int[] nums, int target) {
        int[] ret = {-1, -1};
        if (nums.length == 0){
            return ret;
        }

        int left = 0, right = nums.length - 1;

        while (left<right){
            // 寻找左侧边界  left + ((right-left)>>1)
            int mid = left + ((right-left)>>1);
            if (target<=nums[mid]){
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        if (nums[left]!=target){
            return ret;
        }
        ret[0] = left;
        right = nums.length - 1;
        while (left<right){
            //寻找右侧边界 left + ((right-left+1)>>1)
            int mid = left + ((right-left+1)>>1);
            if (target>=nums[mid]){
                left = mid ;
            }else {
                right = mid - 1;
            }
        }
        ret[1] = left;
        return ret;

    }


}
